﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;


// 1、跳台阶
//一只青蛙一次可以跳上1级台阶，也可以跳上2级。
//求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。


class Solution
{
public:
    int jumpFloor(int number)
    {
        vector<int> arr(number + 1, 0);
        arr[0] = 1;
        arr[1] = 1;

        // 斐波那契数列
        for (int i = 2; i <= number; ++i)
        {
            arr[i] = arr[i - 1] + arr[i - 2];
        }

        return arr[number];
    }
};


// 2、移动零
//给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

class Solution
{
public:
    void moveZeroes(vector<int>& nums)
    {
        int left = 0;
        int right = 0;
        while (right < nums.size())
        {
            if (nums[right])
            {
                swap(nums[left], nums[right]);
                ++left;
            }

            ++right;
        }

    }
};


// 3、两数之和 II - 输入有序数组
// 
//给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，
//请你从数组中找出满足相加之和等于目标数 target 的两个数。
//如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
//
//    以长度为 2 的整数数组[index1, index2] 的形式返回这两个整数的下标 index1 和 index2。
//
//    你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
//
//    你所设计的解决方案必须只使用常量级的额外空间。


class Solution
{
public:
    vector<int> twoSum(vector<int>& numbers, int target)
    {
        vector<int> arr;
        int left = 0;
        int right = numbers.size() - 1;

        while (left < right)
        {
            if (numbers[left] + numbers[right] > target)
            {
                --right;
            }
            else if (numbers[left] + numbers[right] < target)
            {
                ++left;
            }
            else
            {
                arr.push_back(left + 1);
                arr.push_back(right + 1);
                break;
            }
        }

        return arr;
    }
};


// 4、矩形覆盖
//我们可以用 2 * 1 的小矩形横着或者竖着去覆盖更大的矩形。
//请问用 n 个 2 * 1 的小矩形无重叠地覆盖一个 2 * n 的大矩形，从同一个方向看总共有多少种不同的方法？


class Solution
{
public:
    int rectCover(int number)
    {
        if (number == 0 || number == 1 || number == 2)
        {
            return number;
        }

        int num1 = 1, num2 = 2, rectNum = 0;

        for (int i = 3; i <= number; ++i)
        {
            rectNum = num1 + num2;
            num1 = num2;
            num2 = rectNum;
        }

        return rectNum;
    }
};




// 5、和为S的连续正数序列

//小明很喜欢数学, 有一天他在做数学作业时, 要求计算出9~16的和, 
//他马上就写出了正确答案是100。但是他并不满足于此, 
//他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
//没多久, 他就得到另一组连续正数和为100的序列:18, 19, 20, 21, 22。
//现在把问题交给你, 你能不能也很快的找出所有和为S的连续正数序列 ?


class Solution
{
public:
    vector<vector<int> > FindContinuousSequence(int sum)
    {
        vector<vector<int>> sequence;
        vector<int> arr;

        for (int left = 1, right = 2; left < right; )
        {
            // 计算区间连续和
            int sum1 = (left + right) * (right - left + 1) / 2;

            if (sum1 == sum)
            {
                arr.clear();

                // 记录区间序列
                for (int i = left; i <= right; ++i)
                {
                    arr.push_back(i);
                }
                sequence.push_back(arr);

                ++left;
            }
            else if (sum1 < sum)
            {
                ++right;
            }
            else
            {
                ++left;
            }
        }

        return sequence;
    }
};
